package com.kang.basicalgorithm.twodivide;

import java.util.Collections;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @author xukang
 * @date 2021-10-20 18:22
 * 二分法查找
 * 1 已经排好序的数组 a
 * 2.定义左边界l和右边界R ,确定搜索范围
 * 3.获取中间索引M= Floor((l+r)/2)
 * 4.中间索引值A[M]与待搜索值T比较
 * 1)A[M]==T,表示找到 ,返回中间索引
 * 2)A[M]>T,中间值右侧值都大于T,无需比较,值在左侧,右侧边界设置为M-1,重新查找
 * 3)A[M]<T,中间值左侧值都小于T,无需比较,值在右侧,左侧边界设置为M+1,重新查找
 * 5.当l>=r时,循环结束,没有对应的值
 */
public class TwoDivide {
    public static void main(String[] args) {
//        ConcurrentHashMap<Object, Object> objectObjectConcurrentHashMap = new ConcurrentHashMap<>();
        int[] arr = {1, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 16, 17, 18, 21, 24, 26, 28, 30, 36, 38, 39, 40, 56, 58, 79};
        System.out.println(arr.length);
        int target = 79;
        int i = binarySearch(arr, target);
        System.out.println(i);
//        Collections.binarySearch()
    }

    public static int binarySearch(int[] array, int target) {
        if (array.length > 0 && array != null) {
            int l = 0,m;
            int r = array.length - 1;
            do {
                //解决int超过范围溢出
                //无符号右移 只有正数才能完全等价于除以2
                m = (l + r) >>> 1;
                if (target == array[m]) {
                    return m + 1;
                } else if (target > array[m]) {
                    l = m + 1;
                    System.out.println("l=" + l);
                } else {
                    r = m - 1;
                    System.out.println("r=" + r);
                }
            } while (l <= r);

        }
        return -1;
    }
}
